﻿using System.Collections;
using System.Collections.Generic;

namespace Devil
{
    // 最小堆
    public class MinHeap<T> : ICollection<T>
    {
        private T[] mDatas;
        private bool mIsStruct;
        private int mLength;
        private GetterDelegate<T, int> mComparisonInput;
        private System.Comparison<T> mComparison;
        public System.Comparison<T> Comparision
        {
            get { return mComparison; }
            set
            {
                System.Comparison<T> com;
                if (value == null)
                    com = DefaultCompare;
                else
                    com = value;
                if (com != mComparison)
                {
                    if (mLength > 0)
                        throw new System.InvalidOperationException("The MinHeap's comparision method can not be replaced while having datas.");
                    mComparison = com;
                }
            }
        }

        public GetterDelegate<T, int> ComparisonInput
        {
            get { return mComparisonInput; }
            set
            {
                GetterDelegate<T, int> cinput;
                if (value == null)
                    cinput = DefaultComparisonInput;
                else
                    cinput = value;
                if (cinput != mComparisonInput)
                {
                    if (mLength > 0)
                        throw new System.InvalidOperationException("The MinHeap's comparision input method can not be replaced while having datas.");
                    mComparisonInput = cinput;
                }
            }
        }

        private EquatableDelegate<T> mEquatable;
        public EquatableDelegate<T> Equatable
        {
            get { return mEquatable; }
            set
            {
                if (value == null)
                    mEquatable = DefaultEqual;
                else
                    mEquatable = value;
            }
        }

        public MinHeap(int capacity, System.Comparison<T> comparison = null, EquatableDelegate<T> equatable = null, bool alwaysAsStruct = false)
        {
            mDatas = new T[capacity > 8 ? capacity : 8];
            if (comparison == null)
                mComparison = DefaultCompare;
            else
                mComparison = comparison;
            if (equatable == null)
                mEquatable = DefaultEqual;
            else
                mEquatable = equatable;
            mComparisonInput = DefaultComparisonInput;
            mIsStruct = alwaysAsStruct || typeof(T).IsValueType;
        }

        public MinHeap(int capacity, GetterDelegate<T, int> comparisonInput, EquatableDelegate<T> equatable = null, bool alwaysAsStruct = false)
        {
            mDatas = new T[capacity > 8 ? capacity : 8];
            if (comparisonInput == null)
                mComparisonInput = DefaultComparisonInput;
            else
                mComparisonInput = comparisonInput;
            if (equatable == null)
                mEquatable = DefaultEqual;
            else
                mEquatable = equatable;
            mComparison = DefaultCompare;
            mIsStruct = alwaysAsStruct || typeof(T).IsValueType;
        }

        public int Count { get { return mLength; } }
        public T this[int index] { get { return mDatas[index]; } }
        public T[] RawDatas { get { return mDatas; } }

        int DefaultComparisonInput(T a)
        {
            return a == null ? 0 : a.GetHashCode();
        }

        int DefaultCompare(T a, T b)
        {
            var h1 = mComparisonInput(a);
            var h2 = mComparisonInput(b);
            if (h1 < h2)
                return -1;
            else if (h1 > h2)
                return 1;
            else
                return 0;
        }

        bool DefaultEqual(T a, T b)
        {
            if (a is System.IEquatable<T>)
                return ((System.IEquatable<T>)a).Equals(b);
            else if (mIsStruct || a != null)
                return a.Equals(b);
            else
                return b == null;
        }

        public T TopValule { get { return mDatas[0]; } }

        public bool IsReadOnly { get { return false; } }

        public T SecondValue
        {
            get
            {
                if (mLength < 2)
                    return default;
                if (mLength == 2 || mComparison(mDatas[1], mDatas[2]) <= 0)
                    return mDatas[1];
                else
                    return mDatas[2];
            }
        }

        public void Clear()
        {
            if (!mIsStruct)
            {
                var def = default(T);
                for (int i = 0; i < mLength; i++)
                {
                    mDatas[i] = def;
                }
            }
            mLength = 0;
        }

        public void Cleanup()
        {
            var def = default(T);
            for (int i = 0; i < mLength; i++)
            {
                mDatas[i] = def;
            }
            mLength = 0;
        }

        public bool Contains(T item)
        {
            for (int i = 0; i < mLength; i++)
            {
                if (mEquatable(mDatas[i], item))
                    return true;
            }
            return false;
        }

        public int IndexOf(T item)
        {
            for (int i = 0; i < mLength; i++)
            {
                if (mEquatable(mDatas[i], item))
                    return i;
            }
            return -1;
        }
        public void CopyTo(T[] array, int arrayIndex)
        {
            System.Array.Copy(mDatas, 0, array, arrayIndex, mLength);
        }

        public void Add(T value)
        {
            if (mLength == mDatas.Length)
            {
                var newdata = new T[mLength << 1];
                System.Array.Copy(mDatas, newdata, mLength);
                mDatas = newdata;
            }

            int child = mLength;
            mDatas[mLength++] = value;
            T tmp;
            int parent;
            while (child > 0)
            {
                parent = (child - 1) >> 1;
                if (mComparison(mDatas[parent], mDatas[child]) <= 0)
                    break;
                tmp = mDatas[parent];
                mDatas[parent] = mDatas[child];
                mDatas[child] = tmp;
                child = parent;
            }
        }

        public void AddRange(ICollection<T> values)
        {
            var iter = values.GetEnumerator();
            while (iter.MoveNext())
            {
                Add(iter.Current);
            }
        }

        public T RemoveTop()
        {
            return RemoveAt(0);
        }

        public T RemoveLast()
        {
            if (mLength > 0)
            {
                var t = mDatas[--mLength];
                mDatas[mLength] = default;
                return t;
            }
            return default(T);
        }

        public T RemoveAt(int index)
        {
            var def = default(T);
            if (index >= mLength)
                return def;
            var ret = mDatas[index];
            mDatas[index] = def;
            var tmp = mDatas[--mLength];
            mDatas[mLength] = def;
            int child = (index << 1) + 1;
            int parent;
            while (child < mLength)
            {
                if (child < mLength - 1 && mComparison(mDatas[child], mDatas[child + 1]) > 0)
                    child++;
                parent = (child - 1) >> 1;
                mDatas[parent] = mDatas[child];
                mDatas[child] = def;
                child = (child << 1) + 1;
            }
            child = (child - 1) >> 1;
            mDatas[child] = tmp;
            while (child > 0 && child < mLength)
            {
                parent = (child - 1) >> 1;
                if (mComparison(mDatas[parent], mDatas[child]) <= 0)
                    break;
                tmp = mDatas[parent];
                mDatas[parent] = mDatas[child];
                mDatas[child] = tmp;
                child = parent;
            }
            return ret;
        }

        public bool Remove(T value)
        {
            var index = IndexOf(value);
            if (index >= 0)
            {
                RemoveAt(index);
                return true;
            }
            else
            {
                return false;
            }
        }

        public string ToLayeredString()
        {
            var buf = ParallelUtils.GetBuilder();
            int lv = 0;
            int bros = 0;
            for (int i = 0; i < mLength; i++)
            {
                buf.Append(mDatas[i]).Append(' ');
                if (lv == i)
                {
                    buf.Append('\n');
                    bros++;
                    lv += (1 << bros);
                }
            }
            return ParallelUtils.ReturnRelease(buf);
        }

        #region comparison optimize

        // 返回最小堆中所有最小值
        public void GetTopValues(ICollection<T> topValues)
        {
            if (topValues == null || mLength == 0)
                return;
            GetTopValuesRecursive(topValues, 0);
        }

        void GetTopValuesRecursive(ICollection<T> topValues, int root)
        {
            var dt = mDatas[root];
            topValues.Add(dt);
            var child = (root << 1) + 1;
            if (child < mLength && mComparison(dt, mDatas[child]) == 0)
            {
                GetTopValuesRecursive(topValues, child);
            }
            child = child + 1;
            if (child < mLength && mComparison(dt, mDatas[child]) == 0)
            {
                GetTopValuesRecursive(topValues, child);
            }
        }

        public int CountTopValues()
        {
            var num = 0;
            if (mLength > 0)
                CountTopValuesRecursive(ref num, 0);
            return num;
        }

        void CountTopValuesRecursive(ref int num, int root)
        {
            var dt = mDatas[root];
            num++;
            var child = (root << 1) + 1;
            if (child < mLength && mComparison(dt, mDatas[child]) == 0)
            {
                CountTopValuesRecursive(ref num, child);
            }
            child = child + 1;
            if (child < mLength && mComparison(dt, mDatas[child]) == 0)
            {
                CountTopValuesRecursive(ref num, child);
            }
        }

        // 返回与参考值相同的所有数据
        public void GetNearByValues(ICollection<T> values, int comparisonInput)
        {
            if (values == null || mLength == 0)
                return;
            GetNearByValuesRecursive(values, 0, comparisonInput);
        }

        void GetNearByValuesRecursive(ICollection<T> values, int root, int comparisonInput)
        {
            var dt = mDatas[root];
            var dti = mComparisonInput(dt);
            if (dti > comparisonInput)
                return;
            if (dti == comparisonInput)
                values.Add(dt);
            var child = (root << 1) + 1;
            if (child < mLength)
                GetNearByValuesRecursive(values, child, comparisonInput);
            child += 1;
            if (child < mLength)
                GetNearByValuesRecursive(values, child, comparisonInput);
        }

        public int CountNearByValues(int comparisonInput)
        {
            var num = 0;
            if (mLength > 0)
                CountNearByValuesRecursive(ref num, 0, comparisonInput);
            return num;
        }

        void CountNearByValuesRecursive(ref int num, int root, int comparisonInput)
        {
            var dt = mDatas[root];
            var dti = mComparisonInput(dt);
            if (dti > comparisonInput)
                return;
            if (dti == comparisonInput)
                num++;
            var child = (root << 1) + 1;
            if (child < mLength)
                CountNearByValuesRecursive(ref num, child, comparisonInput);
            child += 1;
            if (child < mLength)
                CountNearByValuesRecursive(ref num, child, comparisonInput);
        }

        public int FastIndexOf(T item, bool checkEqual)
        {
            var index = mLength > 0 ? CompareChildrenIndex(item, 0, checkEqual) : -1;
            return index;
            
        }

        // 通过比较大小判断是否包含（比较相等的节点）
        public bool ComparisonContains(T item, bool checkEqual)
        {
            var index = mLength > 0 ? CompareChildrenIndex(item, 0, checkEqual) : -1;
            return index != -1;
        }

        int CompareChildrenIndex(T item, int root, bool checkEqual)
        {
            var index = mComparison(mDatas[root], item);
            if (index > 0)
                return -1;
            if (index == 0 && (!checkEqual || mEquatable(item, mDatas[root])))
                return root;
            var child = (root << 1) + 1;
            if (child >= mLength)
                return -1;
            index = CompareChildrenIndex(item, child, checkEqual);
            if (index != -1)
                return index;
            child += 1;
            if (child >= mLength)
                return -1;
            return CompareChildrenIndex(item, child, checkEqual);
        }

        public int FindIndexIntoChildren(int comparisonInput)
        {
            return mLength > 0 ? CompareChildrenIndex(comparisonInput, 0) : -1;
        }

        int CompareChildrenIndex(int comparisonInput, int root)
        {
            var input = mComparisonInput(mDatas[root]);
            if (input == comparisonInput)
                return root;
            if (input > comparisonInput)
                return -1;
            var child = (root << 1) + 1;
            if (child >= mLength)
                return -1;
            input = CompareChildrenIndex(comparisonInput, child);
            if (input != -1)
                return input;
            child += 1;
            if (child >= mLength)
                return -1;
            return CompareChildrenIndex(comparisonInput, child);

        }

        #endregion
      
        #region enumerator

        public IEnumerator<T> GetEnumerator()
        {
            return new Enumerator(this);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return new Enumerator(this);
        }

        private struct Enumerator : IEnumerator<T>
        {
            private int mPtr;
            MinHeap<T> mHeap;
            public Enumerator(MinHeap<T> heap)
            {
                mHeap = heap;
                mPtr = -1;
            }

            public T Current { get { return mPtr < mHeap.mLength && mPtr >= 0 ? mHeap.mDatas[mPtr] : default(T); } }

            object IEnumerator.Current { get { return mPtr < mHeap.mLength && mPtr >= 0 ? mHeap.mDatas[mPtr] : default(T); } }

            public void Dispose()
            {
                mHeap = null;
            }

            public bool MoveNext()
            {
                if (++mPtr < mHeap.mLength)
                    return true;
                else
                    return false;
            }

            public void Reset()
            {
                mPtr = -1;
            }
        }

        #endregion
    }
}